package com.leetcode.www;

/**
 * Creared with IntelliJ IDEA.
 * Description:给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 *
 * 请必须使用时间复杂度为 O(log n) 的算法。
 *
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/search-insert-position
 *
 * User:yxd
 * Date:2022-01-12
 * Time:23:37
 */
public class Normal278 {
    public static void main(String[] args) {
        int[] nums = {1,3,5};
        int a = 2;
        System.out.println(searchInsert(nums, a));
    }

    public static int searchInsert(int[] nums, int target) {
        //二分查找
        int n = nums.length;
        int left = 0, right = n - 1, ans = n;
        while (left <= right) {
            int mid = ((right - left) >> 1) + left;//中间点
            if (target <= nums[mid]) {//小于中间的 说明 答案在 左边  向左压缩
                ans = mid;
                right = mid - 1;
            } else {//向右压缩
                left = mid + 1;
            }
        }
        return ans;
    }



    public static int searchInsert1(int[] nums, int target) {
        //从两边同时遍历数组
        int n = nums.length;
        if(n <= 0) return 0;
        int l = 0;
        int r = n - 1;
        while(l <= r){
            if(nums[l] < target){
                l++;
            }else{
                return l;
            }
            if(nums[r] > target){
                r --;
            }else{
                if(target == nums[r]){
                    return r;
                }
                return r + 1;
            }
        }
        if(n == 1){
            if(nums[0] >= target){
                return 0;
            }else{
                return 1;
            }
        }else{
            return l;
        }

    }
}
